{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Multi Search LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #string-matching #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #字符串匹配 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: multiSearch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #多次搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个较长字符串<code>big</code>和一个包含较短字符串的数组<code>smalls</code>，设计一个方法，根据<code>smalls</code>中的每一个较短字符串，对<code>big</code>进行搜索。输出<code>smalls</code>中的字符串在<code>big</code>里出现的所有位置<code>positions</code>，其中<code>positions[i]</code>为<code>smalls[i]</code>出现的所有位置。</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "big = &quot;mississippi&quot;\n",
    "smalls = [&quot;is&quot;,&quot;ppi&quot;,&quot;hi&quot;,&quot;sis&quot;,&quot;i&quot;,&quot;ssippi&quot;]\n",
    "<strong>输出：</strong> [[1,4],[8],[],[3],[1,4,7,10],[5]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= len(big) &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= len(smalls[i]) &lt;= 1000</code></li>\n",
    "\t<li><code>smalls</code>的总字符数不会超过 100000。</li>\n",
    "\t<li>你可以认为<code>smalls</code>中没有重复字符串。</li>\n",
    "\t<li>所有出现的字符均为英文小写字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [multi-search-lcci](https://leetcode.cn/problems/multi-search-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [multi-search-lcci](https://leetcode.cn/problems/multi-search-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"\"\\n[\"a\",\"b\",\"c\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        n = len(big)\n",
    "        start = [[] for _ in range(26)]\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            idx = ord(big[i]) - ord('a')\n",
    "            start[idx].append(i)\n",
    "        for i in range(len(smalls)):\n",
    "            tmp = []\n",
    "            query = smalls[i]\n",
    "            if len(query) == 0:\n",
    "                res.append(tmp.copy())\n",
    "                continue\n",
    "            firstch = query[0]\n",
    "            for idx in start[ord(firstch)-ord('a')]:\n",
    "                if idx + len(smalls[i]) <= n and big[idx:idx+len(smalls[i])] == smalls[i]:\n",
    "                    tmp.append(idx)\n",
    "            res.append(tmp.copy())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        dic = defaultdict(list)\n",
    "        res = []\n",
    "        for index,s in enumerate(big):\n",
    "            dic[s].append(index)\n",
    "        for word in smalls:\n",
    "            n = len(word)\n",
    "            temp = []\n",
    "            if word and word[0] in dic:\n",
    "                for i in dic[word[0]]:\n",
    "                    if big[i:i+n] == word:\n",
    "                        temp.append(i)\n",
    "            res.append(temp)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        pos_dict = defaultdict(list)\n",
    "        for idx, ch in enumerate(big):\n",
    "            pos_dict[ch].append(idx)\n",
    "        big_len = len(big)\n",
    "        rst = [[] for _ in range(len(smalls))]\n",
    "        for idx, small in enumerate(smalls):\n",
    "            if not small or small[0] not in pos_dict:\n",
    "                continue\n",
    "            else:\n",
    "                for pos in pos_dict[small[0]]:\n",
    "                    if big_len - pos >= len(small) and big[pos:pos+len(small)] == small:\n",
    "                        rst[idx].append(pos)\n",
    "\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        dic = defaultdict(list)\n",
    "        res = []\n",
    "        for i,x in enumerate(big):\n",
    "            dic[x].append(i)\n",
    "        for k in smalls:\n",
    "            n = len(k)\n",
    "            temp = []\n",
    "            if k and k[0] in dic:\n",
    "                for j in dic[k[0]]:\n",
    "                    if big[j:j+n] == k:\n",
    "                        temp.append(j)\n",
    "            res.append(temp)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        dic = defaultdict(list)\n",
    "        res = []\n",
    "        for index,s in enumerate(big):\n",
    "            dic[s].append(index)\n",
    "        for word in smalls:\n",
    "            n = len(word)\n",
    "            temp = []\n",
    "            if word and word[0] in dic:\n",
    "                for i in dic[word[0]]:\n",
    "                    if big[i:i+n] == word:\n",
    "                        temp.append(i)\n",
    "            res.append(temp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "\t\tans = [[] for _ in range(len(smalls))]\n",
    "\t\tfor i in range(len(big)):\n",
    "\t\t\tsub = big[i:]\n",
    "\t\t\tfor index, value in enumerate(smalls):\n",
    "\t\t\t\tif value and sub.startswith(value):\n",
    "\t\t\t\t\tans[index].append(i)\n",
    "\t\treturn ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        s2idx = {}\n",
    "        n = len(big)\n",
    "        lens = set()\n",
    "        for s in smalls:\n",
    "            s2idx[s] = []\n",
    "            lens.add(len(s))\n",
    "        \n",
    "        for i in range(n):\n",
    "            for d in lens:\n",
    "                # print(i, d, big[i:i+d])\n",
    "                if d > 0 and i + d <= n and big[i:i+d] in s2idx:\n",
    "                    s2idx[big[i:i+d]].append(i)\n",
    "        return list(s2idx.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        s2idx = {}\n",
    "        n = len(big)\n",
    "        lens = set()\n",
    "        for s in smalls:\n",
    "            s2idx[s] = []\n",
    "            lens.add(len(s))\n",
    "        \n",
    "        for i in range(n):\n",
    "            for d in lens:\n",
    "                # print(i, d, big[i:i+d])\n",
    "                if d > 0 and i + d <= n and big[i:i+d] in s2idx:\n",
    "                    s2idx[big[i:i+d]].append(i)\n",
    "        return list(s2idx.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        for i in range(len(word)):\n",
    "            node = self.children\n",
    "            for ch in word[i]:\n",
    "                if ch not in node.keys():\n",
    "                    node[ch] = dict()\n",
    "                node = node[ch]\n",
    "            node['end'] = i\n",
    "\n",
    "    def search(self, word):\n",
    "        node = self.children\n",
    "        res = []\n",
    "        for ch in word:\n",
    "            if ch not in node.keys():\n",
    "                return res\n",
    "            node = node[ch]\n",
    "            if 'end' in node.keys():\n",
    "                res.append(node['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie()\n",
    "        trie.insert(smalls)\n",
    "        res = [[] for _ in range(len(smalls))]\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            temp = trie.search(big[i:])\n",
    "            for idx in temp:\n",
    "                res[idx].append(i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "   def __init__(self, words):\n",
    "       self.d = {}\n",
    "       for i in range(len(words)):\n",
    "           tree = self.d\n",
    "           for char in words[i]:\n",
    "               if char not in tree:\n",
    "                   tree[char] = {}\n",
    "               tree = tree[char]\n",
    "           tree['end'] = i\n",
    "       \n",
    "   def search(self, s):\n",
    "       tree = self.d\n",
    "       res = []\n",
    "       for char in s:\n",
    "           if char not in tree:\n",
    "               return res\n",
    "           tree = tree[char]\n",
    "           if 'end' in tree:\n",
    "               res.append(tree['end'])\n",
    "       return res\n",
    "\n",
    "class Solution:\n",
    "   def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "       trie = Trie(smalls)\n",
    "       res = [[] for _ in range(len(smalls))]\n",
    "       for i in range(len(big)):\n",
    "           tmp = trie.search(big[i:])\n",
    "           for idx in tmp:\n",
    "               res[idx].append(i)\n",
    "       return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self,words):\n",
    "        self.trie = {}\n",
    "        for idx,word in enumerate(words):\n",
    "            trie = self.trie\n",
    "            for w in word:\n",
    "                if w not in trie:\n",
    "                    trie[w]={}\n",
    "                trie = trie[w]\n",
    "            trie['end']=idx\n",
    "    def search(self,words):\n",
    "        trie = self.trie\n",
    "        res  =[]\n",
    "\n",
    "        for i in words:\n",
    "            if i  not in trie: return  res\n",
    "            trie = trie[i]\n",
    "            if \"end\" in trie:\n",
    "                res.append(trie['end'])\n",
    "        return res\n",
    "\n",
    "\n",
    "                    \n",
    "        \n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        ans = [[] for _ in range(len(smalls))]\n",
    "        for  i in range(len(big)):\n",
    "            tmp = trie.search(big[i:])\n",
    "            for _ in tmp:\n",
    "                ans[_].append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.用 smalls 中的字符串构建字典树 Trie，末尾记录字符串在 smalls 中的位置，方便后面记录字符串在 big 里对应的位置。 2.Trie 中的 search 用于搜索字符串，将搜索到的字符串在 smalls 中的位置存入返回值中。 3.以长字符串 big 中每一位 idx 为开头构建新字符串 big[idx:] ,将其与 Trie 匹配，对匹配到的 smalls 中的字符串记录对应位置idx。\n",
    "'''\n",
    "class Trie:\n",
    "   def __init__(self, words):\n",
    "       self.d = {}\n",
    "       for i in range(len(words)):\n",
    "           tree = self.d\n",
    "           for char in words[i]:\n",
    "               if char not in tree:\n",
    "                   tree[char] = {}\n",
    "               tree = tree[char]\n",
    "           tree['end'] = i\n",
    "       \n",
    "   def search(self, s):\n",
    "       tree = self.d\n",
    "       res = []\n",
    "       for char in s:\n",
    "           if char not in tree:\n",
    "               return res\n",
    "           tree = tree[char]\n",
    "           if 'end' in tree:\n",
    "               res.append(tree['end'])\n",
    "       return res\n",
    "\n",
    "class Solution:\n",
    "   def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "       trie = Trie(smalls)\n",
    "       res = [[] for _ in range(len(smalls))]\n",
    "       for i in range(len(big)):\n",
    "           tmp = trie.search(big[i:])\n",
    "           for idx in tmp:\n",
    "               res[idx].append(i)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self, words):\n",
    "\n",
    "        self.d = {}\n",
    "\n",
    "        for word in words:\n",
    "\n",
    "            t = self.d\n",
    "\n",
    "            for w in word:\n",
    "\n",
    "                if w not in t:\n",
    "\n",
    "                    t[w] = {}\n",
    "\n",
    "                t = t[w]\n",
    "\n",
    "            t['end'] = word\n",
    "\n",
    "    \n",
    "\n",
    "    def search(self, s):\n",
    "\n",
    "        t = self.d\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for w in s:\n",
    "\n",
    "            if w not in t:\n",
    "\n",
    "                break\n",
    "\n",
    "            t = t[w]\n",
    "\n",
    "            if 'end' in t:\n",
    "\n",
    "                res.append(t['end'])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "\n",
    "        trie = Trie(smalls)\n",
    "\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(len(big)):\n",
    "\n",
    "            matchs = trie.search(big[i:])\n",
    "\n",
    "            for word in matchs:\n",
    "\n",
    "                hit[word].append(i)\n",
    "\n",
    "        \n",
    "\n",
    "        res = []\n",
    "\n",
    "        for word in smalls:\n",
    "\n",
    "            res.append(hit[word])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self,words):\n",
    "        self.dic = {}\n",
    "        for word in words:\n",
    "            t = self.dic\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    def search(self,s):\n",
    "        t = self.dic\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路\n",
    "# trie中记录smalls中的字符串，末尾记录字符串，方便后面遍历。\n",
    "# trie中的search用于搜索字符串，将搜索到的字符串存入返回值中。\n",
    "# 遍历big长字符串，将其与trie匹配。\n",
    "# 按smalls顺序输出最终结果\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "        \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "\n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words): # trie中记录smalls中的字符串，末尾记录字符串，方便后面遍历。\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s): # trie中的search用于搜索字符串，将搜索到的字符串存入返回值中。\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls) \n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)): # 遍历big长字符串，将其与trie匹配。\n",
    "            matchs = trie.search(big[i:]) # 以big[i]开头能构成哪些smalls中的单词 \n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls: # 按smalls顺序输出最终结果。\n",
    "            res.append(hit[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, words):\n",
    "        self.d = {}\n",
    "        for word in words:\n",
    "            t = self.d\n",
    "            for w in word:\n",
    "                if w not in t:\n",
    "                    t[w] = {}\n",
    "                t = t[w]\n",
    "            t['end'] = word\n",
    "    \n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w not in t:\n",
    "                break\n",
    "            t = t[w]\n",
    "            if 'end' in t:\n",
    "                res.append(t['end'])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        hit = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            matchs = trie.search(big[i:])\n",
    "            for word in matchs:\n",
    "                hit[word].append(i)\n",
    "        \n",
    "        res = []\n",
    "        for word in smalls:\n",
    "            res.append(hit[word])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie_tree = {}\n",
    "\n",
    "        for i, word in enumerate(smalls):\n",
    "            root = trie_tree\n",
    "            for c in word:\n",
    "                if not c in root:\n",
    "                    root[c] = {}\n",
    "                root = root[c]\n",
    "            if \"$\" not in root:\n",
    "                root[\"$\"] = []\n",
    "            root[\"$\"].append(i)\n",
    "\n",
    "        ret = [[] for _ in smalls]\n",
    "        for i in range(len(big)):\n",
    "            word = big[i:]\n",
    "            root = trie_tree\n",
    "            searched_idx = []\n",
    "            for c in word:\n",
    "                if c not in root:\n",
    "                    break\n",
    "                root = root[c]\n",
    "                if \"$\" in root:\n",
    "                    searched_idx.extend(root[\"$\"])\n",
    "            for idx in searched_idx:\n",
    "                ret[idx].append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(big)\n",
    "        for w in smalls:\n",
    "            if w == \"\":\n",
    "                ans.append([])\n",
    "                continue\n",
    "            i = 0\n",
    "            index = []\n",
    "            while i < n:\n",
    "                find = big.find(w, i)\n",
    "                if find == -1:\n",
    "                    break\n",
    "                index.append(find)\n",
    "                i = find + 1\n",
    "            ans.append(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        result = []\n",
    "        if smalls == ['']:\n",
    "            return [[]]\n",
    "        for sub in smalls:\n",
    "            list_ = []\n",
    "            if sub in big:\n",
    "                for i in range(len(big)):\n",
    "                    if sub == big[i:len(sub)+i]:\n",
    "                        list_.append(i)\n",
    "            result.append(list_)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        result=[]\n",
    "        for small in smalls:\n",
    "            cur=[]\n",
    "            n=len(small)\n",
    "            if n>0:\n",
    "                for index in range(len(big)):\n",
    "                    if len(big)-index<n:\n",
    "                        break\n",
    "                    elif big[index:index+n]==small:\n",
    "                        cur.append(index)\n",
    "            result.append(cur[:])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        dictionary = {small: [] for small in smalls if small}\n",
    "        if len(dictionary) == 0:\n",
    "            return [[]]\n",
    "\n",
    "        smalls.sort(key=len)\n",
    "        minimum, maximum = len(smalls[0]), len(smalls[-1])\n",
    "        for size in range(minimum, maximum + 1):\n",
    "            for i in range(0, len(big) - size + 1):\n",
    "                window = big[i:i + size]\n",
    "                if window in dictionary:\n",
    "                    dictionary[window].append(i)\n",
    "        return list(dictionary.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        for small in smalls:\n",
    "            idx=[]\n",
    "            l=len(small)\n",
    "            if l>0:\n",
    "                for i in range(len(big)-l+1):\n",
    "                    s=big[i:i+l]\n",
    "                    if s == small:\n",
    "                        idx.append(i)\n",
    "            res.append(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "      ## 后缀树\n",
    "        n = len(smalls)\n",
    "        m = len(big)\n",
    "        ans = [[] for _ in range(n)]\n",
    "        for i, s in enumerate(smalls):\n",
    "            t = big\n",
    "            j = 0\n",
    "            if s == '':\n",
    "              continue\n",
    "            while (k := t.find(s)) >= 0:\n",
    "                ans[i].append(j + k)\n",
    "                j += k + 1\n",
    "                t = t[k + 1:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(big)\n",
    "        for w in smalls:\n",
    "            i = 0\n",
    "            index = []\n",
    "            if w != \"\":\n",
    "                while i < n:\n",
    "                    find = big.find(w, i)\n",
    "                    if find == -1:\n",
    "                        break\n",
    "                    index.append(find)\n",
    "                    i = find + 1\n",
    "            ans.append(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = [[] for _ in range(len(smalls))]\n",
    "        n = len(big)\n",
    "        for i, j in enumerate(smalls):\n",
    "            left = 0\n",
    "            right = len(j) - 1\n",
    "            while right >= left and right < n:\n",
    "                if big[left:right + 1] == j:\n",
    "                    ans[i].append(left)\n",
    "                left += 1\n",
    "                right += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        n = len(big)\n",
    "        def oneSearch(s):\n",
    "            ans = []\n",
    "            ls = len(s)\n",
    "            if ls == 0 or n == 0:\n",
    "                return []\n",
    "            i = 0\n",
    "            while i + ls <= n:\n",
    "                if big[i:i+ls] == s:\n",
    "                    ans.append(i)\n",
    "                i += 1\n",
    "            return ans \n",
    "        ans = []\n",
    "        for s in smalls:\n",
    "            ans.append(oneSearch(s))       \n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(big)\n",
    "        for small in smalls:\n",
    "            if not small:\n",
    "                ans.append([])\n",
    "                continue\n",
    "            t = len(small)\n",
    "            item = []\n",
    "            for i in range(n - t + 1):\n",
    "                if big[i:i + t] == small:\n",
    "                    item.append(i)\n",
    "            ans.append(item)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        pos = []\n",
    "        for s in smalls:\n",
    "            l = len(s)\n",
    "            temp = []\n",
    "            if l == 0:\n",
    "                pos.append(temp)\n",
    "                continue\n",
    "            for j in range(len(big)-l+1):\n",
    "                if s == big[j:j+l]:\n",
    "                    temp.append(j)\n",
    "            pos.append(temp)\n",
    "        return pos\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        for small in smalls:\n",
    "            idx=[]\n",
    "            tlen=len(small)\n",
    "            if tlen>0:\n",
    "                for i in range(len(big)-tlen+1):\n",
    "                    if big[i:i+tlen]==small:\n",
    "                        idx.append(i)\n",
    "            res.append(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        # 存放最终结果\n",
    "        result = list()\n",
    "        for i, sigle_small in enumerate(smalls):\n",
    "            # 用于存放smlls中单个字符串在big中出现的索引\n",
    "            sub_result = list()\n",
    "\n",
    "            # find()函数认为空字符串''是所有字符串的子串, 所以要特殊处理\n",
    "            if '' == sigle_small and '' != big:\n",
    "                result.append(sub_result)\n",
    "                continue\n",
    "            if '' == sigle_small and '' == big:\n",
    "                result.append(sub_result)\n",
    "                continue\n",
    "\n",
    "            pos = 0\n",
    "            while True:\n",
    "                index = big.find(sigle_small, pos)\n",
    "                if -1 == index:\n",
    "                    break\n",
    "                else:\n",
    "                    sub_result.append(index)\n",
    "                    pos = index + 1\n",
    "            result.append(sub_result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        lb = []\n",
    "        for s in smalls:\n",
    "            length = len(s)\n",
    "            ls = []\n",
    "            if s != \"\":\n",
    "                for i in range(len(big)-length+1):\n",
    "                    if big[i:i+length] == s:\n",
    "                        ls.append(i)\n",
    "            lb.append(ls)\n",
    "        return lb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        len_big = len(big)\n",
    "        len_smalls = len(smalls)\n",
    "        res = []\n",
    "\n",
    "        if len_smalls == 0:\n",
    "            return []\n",
    "        for i in range(len_smalls):\n",
    "            len_i = len(smalls[i])\n",
    "            res1 = []\n",
    "            if len_i == 0:\n",
    "                res1 = [] \n",
    "            else:\n",
    "                for j in range(len_big-len_i + 1):\n",
    "                    s1 = smalls[i]\n",
    "                    s2 = big[j:j+len_i]\n",
    "                    if s1 == s2:\n",
    "                        res1.append(j)\n",
    "            res.append(res1.copy())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for w in smalls:\n",
    "            cur_res = []\n",
    "            for i in range(0, len(big)-len(w) + 1):\n",
    "                if len(w) < 1:\n",
    "                    break \n",
    "                # print(big[i: i+len(w)])\n",
    "                if big[i: i+len(w)] == w:\n",
    "                    cur_res.append(i)\n",
    "            res.append(cur_res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "\n",
    "        for index, small in enumerate(smalls):\n",
    "            tmp = []\n",
    "            if len(small) == 0:\n",
    "                ans.append(tmp)\n",
    "                continue\n",
    "            \n",
    "            start = 0\n",
    "            while True:\n",
    "                try:\n",
    "                    start = big.index(small, start, len(big))\n",
    "                    tmp.append(start)\n",
    "                    start += 1\n",
    "                except :\n",
    "                    break\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        # 存放最终结果\n",
    "        result = list()\n",
    "        for i, sigle_small in enumerate(smalls):\n",
    "            # 用于存放smlls中单个字符串在big中出现的索引\n",
    "            sub_result = list()\n",
    "            if '' == sigle_small and '' != big:\n",
    "                result.append(sub_result)\n",
    "                continue\n",
    "            if '' == sigle_small and '' == big:\n",
    "                result.append(sub_result)\n",
    "                continue\n",
    "\n",
    "            pos = 0\n",
    "            while True:\n",
    "                index = big.find(sigle_small, pos)\n",
    "                if -1 == index:\n",
    "                    break\n",
    "                else:\n",
    "                    sub_result.append(index)\n",
    "                    pos = index + 1\n",
    "            result.append(sub_result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n =  len(big)\n",
    "        for x in smalls:\n",
    "            ans.append([])\n",
    "            l = len(x)\n",
    "            if l == 0:\n",
    "                continue\n",
    "            for i in range(n-l+1):\n",
    "                if big[i:i+l] == x:\n",
    "                    ans[-1].append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "\n",
    "        list1=[]\n",
    "        if smalls==[\"\"]:\n",
    "            return [[]]\n",
    "        for s in smalls:\n",
    "            n=len(s)\n",
    "            cur=[]\n",
    "            for r in range(len(big)):\n",
    "                if s==big[r:r+n]:\n",
    "                    cur.append(r)\n",
    "            list1.append(cur)\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        # 找到下标，记录下标，继续查找。\n",
    "        result = []\n",
    "\n",
    "        for i in smalls:\n",
    "            each_word = []\n",
    "            init_index = 0\n",
    "            end = len(big)\n",
    "            if i == \"\":\n",
    "                result.append(each_word)\n",
    "                continue\n",
    "\n",
    "            while True:\n",
    "                tmp = big.find(i, init_index, end)\n",
    "                if tmp == -1:\n",
    "                    break\n",
    "                else:\n",
    "                    each_word.append(tmp)\n",
    "                    init_index = tmp + 1\n",
    "            result.append(each_word)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        lenb = len(big)\n",
    "        for small in smalls:\n",
    "            index = []\n",
    "            lens = len(small)\n",
    "            if lens > 0:\n",
    "                for i in range(lenb-lens+1):\n",
    "                    if big[i:i+lens] == small:\n",
    "                        index.append(i)\n",
    "            res.append(index)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        big_len = len(big)\n",
    "        max_windows_size = list(set(len(v) for v in smalls))\n",
    "        # small_set = set()\n",
    "        index_dict = {v:[] for v in smalls }\n",
    "        # print(index_dict)\n",
    "        for i in max_windows_size:\n",
    "            for j in range(i,big_len+1):\n",
    "                index = j-i\n",
    "                if index == j:\n",
    "                    break\n",
    "                t = big[index:j]\n",
    "                # print(t)\n",
    "                if (temp:= index_dict.get(t)) is not None:\n",
    "                    # print('1111')\n",
    "                    temp.append(index)\n",
    "                \n",
    "        return [index_dict.get(v, []) for v in smalls]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        m,n = len(smalls),len(big)\n",
    "        positions = []\n",
    "        for i in range(m):\n",
    "            if not smalls[i]:\n",
    "                positions.append([])\n",
    "                continue\n",
    "            k = len(smalls[i])\n",
    "            res = []\n",
    "            for j in range(n-k+1):\n",
    "                if big[j:j+k]==smalls[i]:\n",
    "                    res.append(j)\n",
    "            positions.append(res)\n",
    "        return positions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        temp = []\n",
    "        res = []\n",
    " \n",
    "        for i in range(len(smalls)):\n",
    "            if len(smalls[i]) == 0:\n",
    "                continue\n",
    "            p=0\n",
    "            while True:\n",
    "                num = big.find(smalls[i],p,len(big))\n",
    "                if num==-1:\n",
    "                    res.append(temp)\n",
    "                    temp  = []\n",
    "                    break\n",
    "                else:\n",
    "                    temp.append(num)\n",
    "                    p=num+1\n",
    "        return [[]] if res==[] else res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        m,n = len(smalls),len(big)\n",
    "        positions = []\n",
    "        for i in range(m):\n",
    "            if not smalls[i]:\n",
    "                positions.append([])\n",
    "                continue\n",
    "            k = len(smalls[i])\n",
    "            res = []\n",
    "            for j in range(n-k+1):\n",
    "                if big[j:j+k]==smalls[i]:\n",
    "                    res.append(j)\n",
    "            positions.append(res)\n",
    "        return positions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for w in smalls:\n",
    "            cur_res = []\n",
    "            for i in range(0, len(big)-len(w) + 1):\n",
    "                if len(w) < 1:\n",
    "                    break \n",
    "                # print(big[i: i+len(w)])\n",
    "                if big[i: i+len(w)] == w:\n",
    "                    cur_res.append(i)\n",
    "            res.append(cur_res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for w in smalls:\n",
    "            cur_res = []\n",
    "            for i in range(0, len(big)-len(w) + 1):\n",
    "                if len(w) < 1:\n",
    "                    break \n",
    "                # print(big[i: i+len(w)])\n",
    "                if big[i: i+len(w)] == w:\n",
    "                    cur_res.append(i)\n",
    "            res.append(cur_res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        result = []\n",
    "        for s in smalls:\n",
    "            if s == \"\":\n",
    "                result.append([])\n",
    "            else:\n",
    "                result.append(self.strStr(big, s))\n",
    "        return result\n",
    "    \n",
    "    def strStr(self, big: str, s: str) -> List[int]:\n",
    "        result = []\n",
    "        nextArr = [0] * len(s)\n",
    "        self.getNext(nextArr, s)\n",
    "        j = 0  # 标记匹配串 第一个没被匹配上的位置或者下次匹配要比较的位置\n",
    "        for i in range(len(big)):\n",
    "            # 不匹配时\n",
    "            while j > 0 and big[i] != s[j]:\n",
    "                j = nextArr[j - 1]\n",
    "            # 匹配时\n",
    "            if big[i] == s[j]:\n",
    "                j += 1\n",
    "            if j == len(s):\n",
    "                result.append(i - len(s) + 1)\n",
    "                j = nextArr[j - 1]\n",
    "        return result\n",
    "    \n",
    "    def getNext(self, nextArr: List[int], s: str):\n",
    "        j = 0  # 最长相当前缀位置+1，标记第一个没被匹配上的位置或者下次匹配要比较的位置\n",
    "        for i in range(1, len(s)):  # 遍历从1开始\n",
    "            # 不匹配时\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = nextArr[j - 1]\n",
    "            # 匹配时\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            nextArr[i] = j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for w in smalls:\n",
    "            cur_res = []\n",
    "            for i in range(0, len(big)-len(w) + 1):\n",
    "                if len(w) < 1:\n",
    "                    break \n",
    "                # print(big[i: i+len(w)])\n",
    "                if big[i: i+len(w)] == w:\n",
    "                    cur_res.append(i)\n",
    "            res.append(cur_res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNext(self, s):\n",
    "        # 建立模式串的next数组\n",
    "        n = len(s)\n",
    "        next = [0]*n\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i+1):\n",
    "                if s[:i].find(s[j:i+1]) > -1:\n",
    "                    next[i] = i-j+1\n",
    "                    break\n",
    "        return next\n",
    "\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for k in range(len(smalls)):\n",
    "            patt = smalls[k]\n",
    "            n = len(patt)\n",
    "\n",
    "            if not patt:\n",
    "                res.append([])\n",
    "                continue\n",
    "\n",
    "            next = self.getNext(patt)\n",
    "            # 搜索 不回溯\n",
    "            tmp = []\n",
    "            j = 0\n",
    "            i = 0\n",
    "            while i < len(big):\n",
    "                # print(i,j)\n",
    "                if big[i] == patt[j]:\n",
    "                    if j==n-1:\n",
    "                        tmp.append(i+1-n)\n",
    "                        if j>0:\n",
    "                            j = next[j-1]\n",
    "                            i -= 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "                else:\n",
    "                    if j>0:\n",
    "                        j = next[j-1]\n",
    "                        i -= 1\n",
    "                i += 1\n",
    "            res.append(tmp)\n",
    "            # print(patt, next, tmp)\n",
    "        \n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        big_len = len(big)\n",
    "        max_windows_size = list(set(len(v) for v in smalls))\n",
    "        # small_set = set()\n",
    "        index_dict = {v:[] for v in smalls }\n",
    "        # print(index_dict)\n",
    "        for i in max_windows_size:\n",
    "            for j in range(i,big_len+1):\n",
    "                t = big[j-i:j]\n",
    "                # print(t)\n",
    "                if t and (temp:= index_dict.get(t)) is not None:\n",
    "                    print('1111')\n",
    "                    temp.append(j-i)\n",
    "                \n",
    "        return [index_dict.get(v, []) for v in smalls]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class KMP:\n",
    "    def __init__(self, pattern:str):\n",
    "        self.pattern = pattern\n",
    "        self.match = [0] * len(pattern)\n",
    "        c = 0\n",
    "        for i in range(1, len(pattern)):\n",
    "            v = pattern[i]\n",
    "            while c and pattern[c] != v: c = self.match[c - 1]\n",
    "            if pattern[c] == v: c += 1\n",
    "            self.match[i] = c\n",
    "    \n",
    "    # 返回 text 中出现了多少次 pattern（允许 pattern 重叠）\n",
    "    def get_find_positions(self, text:str)->int:\n",
    "        c = 0\n",
    "        match_positions = []\n",
    "        for i, v in enumerate(text):\n",
    "            v = text[i]\n",
    "            while c and self.pattern[c] != v: c = self.match[c - 1]\n",
    "            if self.pattern[c] == v: c += 1\n",
    "            if c == len(self.pattern):\n",
    "                match_positions.append(i-c+1)\n",
    "                c = self.match[c - 1]\n",
    "        return match_positions\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for x in smalls:\n",
    "            if not x:\n",
    "                ans.append([])\n",
    "                continue\n",
    "            kmp = KMP(pattern=x)\n",
    "            find_pos = kmp.get_find_positions(text=big) # list\n",
    "            ans.append(find_pos)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        big_len = len(big)\n",
    "        max_windows_size = max( big_len if (t:=len(s))>big_len else t  for s in smalls)\n",
    "        small_set = set(smalls)\n",
    "        index_dict = {}\n",
    "        for i in range(1, max_windows_size+1):\n",
    "            for j in range(i,big_len+1):\n",
    "                t = big[j-i:j]\n",
    "                if t not in small_set:\n",
    "                    continue\n",
    "                if t in index_dict:\n",
    "                    index_dict[t].append(j-i)\n",
    "                else:\n",
    "                    index_dict[t] = [j-i]\n",
    "        return [index_dict.get(v, []) for v in smalls]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        big_len = len(big)\n",
    "        max_windows_size = max( big_len if (t:=len(s))>big_len else t  for s in smalls)\n",
    "        small_set = set(smalls)\n",
    "        index_dict = {}\n",
    "        for i in range(1, max_windows_size+1):\n",
    "            for j in range(i,big_len+1):\n",
    "                t = big[j-i:j]\n",
    "                if t not in small_set:\n",
    "                    continue\n",
    "                if t in index_dict:\n",
    "                    index_dict[t].append(j-i)\n",
    "                else:\n",
    "                    index_dict[t] = [j-i]\n",
    "        return [index_dict.get(v, []) for v in smalls]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        positions = []\n",
    "        for small in smalls:\n",
    "            if small == \"\":\n",
    "                positions.append([])\n",
    "                continue\n",
    "            pattern = re.compile(f'(?={small})')\n",
    "            indices = [m.start() for m in pattern.finditer(big)]\n",
    "            positions.append(indices)\n",
    "\n",
    "        return positions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Dict, Generator, List, Tuple, Union\n",
    "\n",
    "INF = int(2e18)\n",
    "\n",
    "\n",
    "class ACAutoMatonMap:\n",
    "    \"\"\"\n",
    "    不调用 BuildSuffixLink 就是Trie,调用 BuildSuffixLink 就是AC自动机.\n",
    "    每个状态对应Trie中的一个结点,也对应一个字符串.\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\n",
    "        \"to\",\n",
    "        \"words\",\n",
    "        \"bfsOrder\",\n",
    "        \"_suffixLink\",\n",
    "    )\n",
    "\n",
    "    def __init__(self):\n",
    "        self.to: List[Dict[str, int]] = [{}]\n",
    "        \"\"\"to[v][c] 表示节点v通过字符c转移到的节点.\"\"\"\n",
    "        self.words = []\n",
    "        \"\"\"words[i] 表示加入的第i个模式串对应的节点编号.\"\"\"\n",
    "        self.bfsOrder = []\n",
    "        \"\"\"结点的拓扑序,0表示虚拟节点.\"\"\"\n",
    "        self._suffixLink = []\n",
    "        \"\"\"又叫fail.指向当前节点最长真后缀对应结点,例如\"bc\"是\"abc\"的最长真后缀.\"\"\"\n",
    "\n",
    "    def addString(self, string: str) -> int:\n",
    "        if not string:\n",
    "            return 0\n",
    "        pos = 0\n",
    "        for char in string:\n",
    "            nexts = self.to[pos]\n",
    "            if char in nexts:\n",
    "                pos = nexts[char]\n",
    "            else:\n",
    "                nextState = len(self.to)\n",
    "                nexts[char] = nextState\n",
    "                pos = nextState\n",
    "                self.to.append({})\n",
    "        self.words.append(pos)\n",
    "        return pos\n",
    "\n",
    "    def addChar(self, pos: int, char: str) -> int:\n",
    "        nexts = self.to[pos]\n",
    "        if char in nexts:\n",
    "            return nexts[char]\n",
    "        nextState = len(self.to)\n",
    "        nexts[char] = nextState\n",
    "        self.to.append({})\n",
    "        return nextState\n",
    "\n",
    "    def move(self, pos: int, char: str) -> int:\n",
    "        to, fail = self.to, self._suffixLink\n",
    "        while True:\n",
    "            nexts = to[pos]\n",
    "            if char in nexts:\n",
    "                return nexts[char]\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            pos = fail[pos]\n",
    "\n",
    "    def buildSuffixLink(self):\n",
    "        \"\"\"\n",
    "        构建后缀链接(失配指针).\n",
    "        \"\"\"\n",
    "        self._suffixLink = [-1] * len(self.to)\n",
    "        self.bfsOrder = [0] * len(self.to)\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            v = self.bfsOrder[head]\n",
    "            head += 1\n",
    "            for char, next_ in self.to[v].items():\n",
    "                self.bfsOrder[tail] = next_\n",
    "                tail += 1\n",
    "                f = self._suffixLink[v]\n",
    "                while f != -1 and char not in self.to[f]:\n",
    "                    f = self._suffixLink[f]\n",
    "                self._suffixLink[next_] = f\n",
    "                if f == -1:\n",
    "                    self._suffixLink[next_] = 0\n",
    "                else:\n",
    "                    self._suffixLink[next_] = self.to[f][char]\n",
    "\n",
    "    def getCounter(self) -> List[int]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的个数.\"\"\"\n",
    "        counter = [0] * len(self.to)\n",
    "        for pos in self.words:\n",
    "            counter[pos] += 1\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                counter[v] += counter[self._suffixLink[v]]\n",
    "        return counter\n",
    "\n",
    "    def getIndexes(self) -> List[List[int]]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的索引.\"\"\"\n",
    "        res = [[] for _ in range(len(self.to))]\n",
    "        for i, pos in enumerate(self.words):\n",
    "            res[pos].append(i)\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                from_, to = self._suffixLink[v], v\n",
    "                arr1, arr2 = res[from_], res[to]\n",
    "                arr3 = [0] * (len(arr1) + len(arr2))\n",
    "                i, j, k = 0, 0, 0\n",
    "                while i < len(arr1) and j < len(arr2):\n",
    "                    if arr1[i] < arr2[j]:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                    elif arr1[i] > arr2[j]:\n",
    "                        arr3[k] = arr2[j]\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    k += 1\n",
    "                while i < len(arr1):\n",
    "                    arr3[k] = arr1[i]\n",
    "                    i += 1\n",
    "                    k += 1\n",
    "                while j < len(arr2):\n",
    "                    arr3[k] = arr2[j]\n",
    "                    j += 1\n",
    "                    k += 1\n",
    "                res[to] = arr3\n",
    "        return res\n",
    "\n",
    "    def dp(self) -> Generator[Tuple[int, int], None, None]:\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                yield self._suffixLink[v], v\n",
    "\n",
    "    @property\n",
    "    def size(self) -> int:\n",
    "        return len(self.to)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 1032. 字符流\n",
    "    # https://leetcode.cn/problems/stream-of-characters/description/\n",
    "    class StreamChecker:\n",
    "        __slots__ = (\"ac\", \"counter\", \"pos\")\n",
    "\n",
    "        def __init__(self, words: List[str]):\n",
    "            self.ac = ACAutoMatonMap()\n",
    "            for word in words:\n",
    "                self.ac.addString(word)\n",
    "            self.ac.buildSuffixLink()\n",
    "            self.counter = self.ac.getCounter()\n",
    "            self.pos = 0\n",
    "\n",
    "        def query(self, letter: str) -> bool:\n",
    "            self.pos = self.ac.move(self.pos, letter)\n",
    "            return self.counter[self.pos] > 0\n",
    "\n",
    "    # https://leetcode.cn/problems/multi-search-lcci/\n",
    "    # 给定一个较长字符串big和一个包含较短字符串的数组smalls，\n",
    "    # 设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。\n",
    "    # !输出smalls中的字符串在big里出现的所有位置positions，\n",
    "    # 其中positions[i]为smalls[i]出现的所有位置。\n",
    "    class Solution:\n",
    "        def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in smalls:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            indexes = acm.getIndexes()\n",
    "            res = [[] for _ in range(len(smalls))]\n",
    "            pos = 0\n",
    "            for i, char in enumerate(big):\n",
    "                pos = acm.move(pos, char)\n",
    "                for index in indexes[pos]:\n",
    "                    res[index].append(i - len(smalls[index]) + 1)\n",
    "            return res\n",
    "\n",
    "\n",
    "# if __name__ == \"__main__\":\n",
    "#     # 2781. 最长合法子字符串的长度\n",
    "#     # https://leetcode.cn/problems/length-of-the-longest-valid-substring/\n",
    "#     # 给你一个字符串 word 和一个字符串数组 forbidden 。\n",
    "#     # 如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。\n",
    "#     # 请你返回字符串 word 的一个 最长合法子字符串 的长度。\n",
    "#     # 子字符串 指的是一个字符串中一段连续的字符，它可以为空。\n",
    "#     #\n",
    "#     # 1 <= word.length <= 1e5\n",
    "#     # word 只包含小写英文字母。\n",
    "#     # 1 <= forbidden.length <= 1e5\n",
    "#     # !1 <= forbidden[i].length <= 1e5\n",
    "#     # !sum(len(forbidden)) <= 1e7\n",
    "#     # forbidden[i] 只包含小写英文字母。\n",
    "#     #\n",
    "#     # 思路:\n",
    "#     # 类似字符流, 需要处理出每个位置为结束字符的包含至少一个模式串的`最短后缀`.\n",
    "#     # !那么此时左端点就对应这个位置+1\n",
    "#     class Solution:\n",
    "#         def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "#             def min(a: int, b: int) -> int:\n",
    "#                 return a if a < b else b\n",
    "\n",
    "#             def max(a: int, b: int) -> int:\n",
    "#                 return a if a > b else b\n",
    "\n",
    "#             acm = ACAutoMatonMap()\n",
    "#             for s in forbidden:\n",
    "#                 acm.addString(s)\n",
    "#             acm.buildSuffixLink()\n",
    "\n",
    "#             minLen = [INF] * acm.size\n",
    "#             for i, pos in enumerate(acm.words):\n",
    "#                 minLen[pos] = min(minLen[pos], len(forbidden[i]))\n",
    "#             for pre, cur in acm.dp():\n",
    "#                 minLen[cur] = min(minLen[cur], minLen[pre])\n",
    "\n",
    "#             res, left, pos = 0, 0, 0\n",
    "#             for right, char in enumerate(word):\n",
    "#                 pos = acm.move(pos, char)\n",
    "#                 left = max(left, right - minLen[pos] + 2)\n",
    "#                 res = max(res, right - left + 1)\n",
    "\n",
    "#             return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self, dic=None):\r\n",
    "        self.value = -1\r\n",
    "        self.child = {}\r\n",
    "        if dic:\r\n",
    "            for i, s in enumerate(dic):\r\n",
    "                self.add(s, i)\r\n",
    "\r\n",
    "    def add(self, s, val):\r\n",
    "        p = self\r\n",
    "        for c in s:\r\n",
    "            if c not in p.child:\r\n",
    "                p.child[c] = Trie()\r\n",
    "            p = p.child[c]\r\n",
    "        p.value = val\r\n",
    "\r\n",
    "    def search(self, s, k, pos):\r\n",
    "        for i in range(k, len(s)):\r\n",
    "            if s[i] not in self.child:\r\n",
    "                return\r\n",
    "            self = self.child[s[i]]\r\n",
    "            if self.value != -1:\r\n",
    "                pos[self.value].append(k)\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\r\n",
    "        trie = Trie(smalls)\r\n",
    "        pos = [[] for _ in range(len(smalls))]\r\n",
    "        for k in range(len(big)):\r\n",
    "            trie.search(big, k, pos)\r\n",
    "        return pos\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self, dic=None):\r\n",
    "        self.value = -1\r\n",
    "        self.child = {}\r\n",
    "        if dic:\r\n",
    "            for i, s in enumerate(dic):\r\n",
    "                self.add(s, i)\r\n",
    "\r\n",
    "    def add(self, s, val):\r\n",
    "        p = self\r\n",
    "        for c in s:\r\n",
    "            if c not in p.child:\r\n",
    "                p.child[c] = Trie()\r\n",
    "            p = p.child[c]\r\n",
    "        p.value = val\r\n",
    "\r\n",
    "    def search(self, s, k, pos):\r\n",
    "        for i in range(k, len(s)):\r\n",
    "            if s[i] not in self.child:\r\n",
    "                return\r\n",
    "            self = self.child[s[i]]\r\n",
    "            if self.value != -1:\r\n",
    "                pos[self.value].append(k)\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\r\n",
    "        trie = Trie(smalls)\r\n",
    "        pos = [[] for _ in range(len(smalls))]\r\n",
    "        for k in range(len(big)):\r\n",
    "            trie.search(big, k, pos)\r\n",
    "        return pos\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, dic=None):\n",
    "        self.value = -1\n",
    "        self.child = {}\n",
    "        if dic:\n",
    "            for i, s in enumerate(dic):\n",
    "                self.add(s, i)\n",
    "\n",
    "    def add(self, s, val):\n",
    "        p = self\n",
    "        for c in s:\n",
    "            if c not in p.child:\n",
    "                p.child[c] = Trie()\n",
    "            p = p.child[c]\n",
    "        p.value = val\n",
    "\n",
    "    def search(self, s, k, pos):\n",
    "        for i in range(k, len(s)):\n",
    "            if s[i] not in self.child:\n",
    "                return\n",
    "            self = self.child[s[i]]\n",
    "            if self.value != -1:\n",
    "                pos[self.value].append(k)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie(smalls)\n",
    "        pos = [[] for _ in range(len(smalls))]\n",
    "        for k in range(len(big)):\n",
    "            trie.search(big, k, pos)\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self, dic=None):\r\n",
    "        self.value = -1\r\n",
    "        self.child = {}\r\n",
    "        if dic:\r\n",
    "            for i, s in enumerate(dic):\r\n",
    "                self.add(s, i)\r\n",
    "\r\n",
    "    def add(self, s, val):\r\n",
    "        p = self\r\n",
    "        for c in s:\r\n",
    "            if c not in p.child:\r\n",
    "                p.child[c] = Trie()\r\n",
    "            p = p.child[c]\r\n",
    "        p.value = val\r\n",
    "\r\n",
    "    def search(self, s, k, pos):\r\n",
    "        for i in range(k, len(s)):\r\n",
    "            if s[i] not in self.child:\r\n",
    "                return\r\n",
    "            self = self.child[s[i]]\r\n",
    "            if self.value != -1:\r\n",
    "                pos[self.value].append(k)\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\r\n",
    "        trie = Trie(smalls)\r\n",
    "        pos = [[] for _ in range(len(smalls))]\r\n",
    "        for k in range(len(big)):\r\n",
    "            trie.search(big, k, pos)\r\n",
    "        return pos\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_word = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            if ch not in node.children:\n",
    "                node.children[ch] = TrieNode()\n",
    "            node = node.children[ch]\n",
    "        node.is_word = True\n",
    "        \n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie()\n",
    "        for word in smalls:\n",
    "            trie.insert(word)\n",
    "        res = [[] for _ in range(len(smalls))]\n",
    "        pos = {v: i for i, v in enumerate(smalls)}\n",
    "        for i in range(len(big)):\n",
    "            node = trie.root\n",
    "            j = i\n",
    "            while j < len(big) and big[j] in node.children:\n",
    "                node = node.children[big[j]] \n",
    "                if node.is_word:\n",
    "                    res[pos[big[i:j+1]]].append(i)\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class wordTree():\n",
    "    def __init__(self,val):\n",
    "        self.val=val\n",
    "        self.nextnode=dict() #子节点用字典存储，方便获取和查询\n",
    "        self.end=False\n",
    "        self.id=-1 #单词在列表的位置\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        size=len(big)\n",
    "        head=wordTree('#')\n",
    "        for i,word in enumerate(smalls):\n",
    "            curnode=head\n",
    "            for w in word:\n",
    "                if w not in curnode.nextnode:\n",
    "                    curnode.nextnode[w]=wordTree(w)\n",
    "                curnode=curnode.nextnode[w]\n",
    "            curnode.end=True\n",
    "            curnode.id=i\n",
    "        res=[[] for i in range(len(smalls))]\n",
    "        for i,ch in enumerate(big):\n",
    "            index=i\n",
    "            curnode=head\n",
    "            while True:\n",
    "                if index >=size or big[index] not in curnode.nextnode:\n",
    "                    break\n",
    "                curnode=curnode.nextnode[big[index]]\n",
    "                if curnode.end:\n",
    "                    res[curnode.id].append(i)\n",
    "                index+=1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Generator, List, Tuple, Union\n",
    "\n",
    "\n",
    "class ACAutoMatonArray:\n",
    "    \"\"\"\n",
    "    不调用 BuildSuffixLink 就是Trie,调用 BuildSuffixLink 就是AC自动机.\n",
    "    每个状态对应Trie中的一个结点,也对应一个字符串.\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\n",
    "        \"to\",\n",
    "        \"words\",\n",
    "        \"bfsOrder\",\n",
    "        \"nodeCount\",\n",
    "        \"_sigma\",\n",
    "        \"_offset\",\n",
    "        \"_parent\",\n",
    "        \"_suffixLink\",\n",
    "    )\n",
    "\n",
    "    def __init__(self, sigma=26, offset=97):\n",
    "        self.to = []\n",
    "        \"\"\"to[v][c] 表示节点v通过字符c转移到的节点.\"\"\"\n",
    "        self.words = []\n",
    "        \"\"\"words[i] 表示加入的第i个模式串对应的节点编号.\"\"\"\n",
    "        self.bfsOrder = []\n",
    "        \"\"\"结点的拓扑序,0表示虚拟节点.\"\"\"\n",
    "        self.nodeCount = 0\n",
    "        \"\"\"自动机中的节点数量,包括虚拟节点0.\"\"\"\n",
    "        self._sigma = sigma\n",
    "        \"\"\"字符集大小.\"\"\"\n",
    "        self._offset = offset\n",
    "        \"\"\"字符集的偏移量.\"\"\"\n",
    "        self._parent = []\n",
    "        \"\"\"parent[v] 表示节点v的父节点.\"\"\"\n",
    "        self._suffixLink = []\n",
    "        \"\"\"又叫fail.指向当前节点最长真后缀对应结点,例如\"bc\"是\"abc\"的最长真后缀.\"\"\"\n",
    "        self._newNode()\n",
    "\n",
    "    def addString(self, string: str) -> int:\n",
    "        if not string:\n",
    "            return 0\n",
    "        pos = 0\n",
    "        for s in string:\n",
    "            ord_ = ord(s) - self._offset\n",
    "            tmp = self.to[pos]\n",
    "            if tmp[ord_] == -1:\n",
    "                tmp[ord_] = self._newNode()\n",
    "                self._parent.append(pos)\n",
    "            pos = tmp[ord_]\n",
    "        self.words.append(pos)\n",
    "        return pos\n",
    "\n",
    "    def addChar(self, pos: int, char: Union[int, str]) -> int:\n",
    "        if isinstance(char, str):\n",
    "            char = ord(char)\n",
    "        char -= self._offset\n",
    "        tmp = self.to[pos]\n",
    "        if tmp[char] != -1:\n",
    "            return tmp[char]\n",
    "        tmp[char] = self._newNode()\n",
    "        self._parent.append(pos)\n",
    "        return tmp[char]\n",
    "\n",
    "    def move(self, pos: int, char: Union[int, str]) -> int:\n",
    "        if isinstance(char, str):\n",
    "            char = ord(char)\n",
    "        return self.to[pos][char - self._offset]\n",
    "\n",
    "    def buildSuffixLink(self, needUpdateTo=True):\n",
    "        \"\"\"\n",
    "        构建后缀链接(失配指针).\n",
    "        needUpdateTo 表示是否需要更新To数组.\n",
    "        \"\"\"\n",
    "        self._suffixLink = [-1] * self.nodeCount\n",
    "        self.bfsOrder = [0] * self.nodeCount\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            v = self.bfsOrder[head]\n",
    "            head += 1\n",
    "            for i, next in enumerate(self.to[v]):\n",
    "                if next == -1:\n",
    "                    continue\n",
    "                self.bfsOrder[tail] = next\n",
    "                tail += 1\n",
    "                f = self._suffixLink[v]\n",
    "                while f != -1 and self.to[f][i] == -1:\n",
    "                    f = self._suffixLink[f]\n",
    "                self._suffixLink[next] = f\n",
    "                if f == -1:\n",
    "                    self._suffixLink[next] = 0\n",
    "                else:\n",
    "                    self._suffixLink[next] = self.to[f][i]\n",
    "        if not needUpdateTo:\n",
    "            return\n",
    "        for v in self.bfsOrder:\n",
    "            tmp = self.to[v]\n",
    "            for i, next in enumerate(tmp):\n",
    "                if next == -1:\n",
    "                    f = self._suffixLink[v]\n",
    "                    if f == -1:\n",
    "                        tmp[i] = 0\n",
    "                    else:\n",
    "                        tmp[i] = self.to[f][i]\n",
    "\n",
    "    def getCounter(self) -> List[int]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的个数.\"\"\"\n",
    "        counter = [0] * self.nodeCount\n",
    "        for pos in self.words:\n",
    "            counter[pos] += 1\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                counter[v] += counter[self._suffixLink[v]]\n",
    "        return counter\n",
    "\n",
    "    def getIndexes(self) -> List[List[int]]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的索引.\"\"\"\n",
    "        res = [[] for _ in range(self.nodeCount)]\n",
    "        for i, pos in enumerate(self.words):\n",
    "            res[pos].append(i)\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                from_, to = self._suffixLink[v], v\n",
    "                arr1, arr2 = res[from_], res[to]\n",
    "                arr3 = [0] * (len(arr1) + len(arr2))\n",
    "                i, j, k = 0, 0, 0\n",
    "                while i < len(arr1) and j < len(arr2):\n",
    "                    if arr1[i] < arr2[j]:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                    elif arr1[i] > arr2[j]:\n",
    "                        arr3[k] = arr2[j]\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    k += 1\n",
    "                while i < len(arr1):\n",
    "                    arr3[k] = arr1[i]\n",
    "                    i += 1\n",
    "                    k += 1\n",
    "                while j < len(arr2):\n",
    "                    arr3[k] = arr2[j]\n",
    "                    j += 1\n",
    "                    k += 1\n",
    "                res[to] = arr3\n",
    "        return res\n",
    "\n",
    "    def dp(self) -> Generator[Tuple[int, int], None, None]:\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                yield self._suffixLink[v], v\n",
    "\n",
    "    @property\n",
    "    def size(self) -> int:\n",
    "        return self.nodeCount\n",
    "\n",
    "    def _newNode(self):\n",
    "        self._parent.append(-1)\n",
    "        nexts = [-1] * self._sigma\n",
    "        self.to.append(nexts)\n",
    "        self.nodeCount += 1\n",
    "        return self.nodeCount - 1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 1032. 字符流\n",
    "    # https://leetcode.cn/problems/stream-of-characters/description/\n",
    "    class StreamChecker:\n",
    "        __slots__ = (\"ac\", \"counter\", \"pos\")\n",
    "\n",
    "        def __init__(self, words: List[str]):\n",
    "            self.ac = ACAutoMatonArray()\n",
    "            for word in words:\n",
    "                self.ac.addString(word)\n",
    "            self.ac.buildSuffixLink()\n",
    "            self.counter = self.ac.getCounter()\n",
    "            self.pos = 0\n",
    "\n",
    "        def query(self, letter: str) -> bool:\n",
    "            self.pos = self.ac.move(self.pos, letter)\n",
    "            return self.counter[self.pos] > 0\n",
    "\n",
    "    # https://leetcode.cn/problems/multi-search-lcci/\n",
    "    # 给定一个较长字符串big和一个包含较短字符串的数组smalls，\n",
    "    # 设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。\n",
    "    # !输出smalls中的字符串在big里出现的所有位置positions，\n",
    "    # 其中positions[i]为smalls[i]出现的所有位置。\n",
    "    class Solution:\n",
    "        def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "            acm = ACAutoMatonArray(sigma=26, offset=97)\n",
    "            for s in smalls:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            indexes = acm.getIndexes()\n",
    "            res = [[] for _ in range(len(smalls))]\n",
    "            pos = 0\n",
    "            for i, char in enumerate(big):\n",
    "                pos = acm.move(pos, char)\n",
    "                for index in indexes[pos]:\n",
    "                    res[index].append(i - len(smalls[index]) + 1)\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Node:\n",
    "        def __init__(self):\n",
    "            self.nexts = [None] * 26\n",
    "            self.wordIdx = -1\n",
    "    global root\n",
    "    root = Node()\n",
    "\n",
    "    def insert(self, word, i):\n",
    "        global root\n",
    "        cur = root\n",
    "        for c in word:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if cur.nexts[idx] is None:\n",
    "                cur.nexts[idx] = self.Node()\n",
    "            cur = cur.nexts[idx]\n",
    "        cur.wordIdx = i\n",
    "\n",
    "    def find(self, word, ret, i):\n",
    "        global root\n",
    "        cur = root\n",
    "        for c in word:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if cur.nexts[idx] is None:\n",
    "                return -1\n",
    "            cur = cur.nexts[idx]\n",
    "            if cur.wordIdx > -1:\n",
    "                # print(f'word:{word}, idx:{cur.wordIdx},cur: {cur}')\n",
    "                ret[cur.wordIdx].append(i)\n",
    "        # return cur.wordIdx\n",
    "\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        global root\n",
    "        root = self.Node()\n",
    "        n, size = len(smalls), len(big)\n",
    "        ret = [[] for _ in range(n)]\n",
    "        if n == \"\":\n",
    "            return ret\n",
    "\n",
    "        for i in range(n):\n",
    "            if len(smalls[i]) == 0:\n",
    "                self.insert(smalls[i], -1)\n",
    "            self.insert(smalls[i], i)\n",
    "        \n",
    "        for i in range(size):\n",
    "            self.find(big[i:size], ret, i)\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class TrieNode:\n",
    "        def __init__(self):\n",
    "            self.children = [None] * 26  # 存储子节点\n",
    "            self.isWord = False  # 标记是否为单词的结束\n",
    "            self.id = 0  # 存储小字符串的索引\n",
    "\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        root = self.TrieNode()  # 初始化根节点\n",
    "        \n",
    "        n = len(smalls)\n",
    "        res = [[] for _ in range(n)]  # 初始化结果集\n",
    "        \n",
    "        # 建树\n",
    "        for i in range(n):\n",
    "            self.insert(root, smalls[i], i)  # 插入小字符串到 Trie 树中\n",
    "        \n",
    "        for i in range(len(big)):\n",
    "            tmp = root\n",
    "            for j in range(i, len(big)):\n",
    "                if not tmp.children[ord(big[j]) - ord('a')]:\n",
    "                    break  # 如果当前字符不存在于 Trie 树中，退出循环\n",
    "                \n",
    "                tmp = tmp.children[ord(big[j]) - ord('a')]\n",
    "                \n",
    "                if tmp.isWord:\n",
    "                    res[tmp.id].append(i)  # 将找到的索引添加到结果集\n",
    "        \n",
    "        # 返回二维数组\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            ret.append(res[i])\n",
    "        \n",
    "        return ret\n",
    "\n",
    "    def insert(self, root: TrieNode, word: str, id: int):\n",
    "        tmp = root\n",
    "        for i in range(len(word)):\n",
    "            if not tmp.children[ord(word[i]) - ord('a')]:\n",
    "                tmp.children[ord(word[i]) - ord('a')] = self.TrieNode()  # 创建新的节点\n",
    "            \n",
    "            tmp = tmp.children[ord(word[i]) - ord('a')]\n",
    "        \n",
    "        tmp.isWord = True  # 标记为一个单词的结束\n",
    "        tmp.id = id  # 存储小字符串的索引\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.is_end = False\n",
    "\n",
    "    def add_word(self, word):\n",
    "        cur_node = self\n",
    "        for c in word:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if not cur_node.children[idx]:\n",
    "                cur_node.children[idx] = Trie()\n",
    "            cur_node = cur_node.children[idx]\n",
    "        cur_node.is_end = True\n",
    "\n",
    "    def search_word(self, target):\n",
    "        cur_node = self\n",
    "        res = []\n",
    "        cur_path = []\n",
    "        for c in target:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if not cur_node.children[idx]:\n",
    "                break\n",
    "            cur_node = cur_node.children[idx]\n",
    "            cur_path.append(c)\n",
    "            if cur_node.is_end:\n",
    "                res.append(''.join(cur_path))\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        trie = Trie()\n",
    "        for word in smalls:\n",
    "            trie.add_word(word)\n",
    "\n",
    "        hit = defaultdict(list)\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            res = trie.search_word(big[i:])\n",
    "            for word in res:\n",
    "                hit[word].append(i)\n",
    "\n",
    "        ans = [hit[word] for word in smalls]\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\"mis\"\n",
    "[\"is\"]\n",
    "\"\"\n",
    "[\"a\",\"b\",\"c\"]\n",
    "\"mississippi\"\n",
    "[\"is\",\"ppi\",\"hi\",\"sis\",\"i\",\"ssippi\"]\n",
    "\n",
    "0 <= len(big) <= 1000\n",
    "0 <= len(smalls[i]) <= 1000\n",
    "The total number of characters in smalls will not exceed 100000.\n",
    "No duplicated strings in smalls.\n",
    "All characters are lowercase letters.\n",
    "\"\"\"\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.c = [None]*26\n",
    "        self.ptr = -1\n",
    "        self.size = -1\n",
    "    def insert(self, w, ptr):\n",
    "        curr = self\n",
    "        for ch in w:\n",
    "            key = ord(ch)-ord('a')\n",
    "            if curr.c[key] is None:\n",
    "                curr.c[key] = TrieNode()\n",
    "            curr = curr.c[key]\n",
    "        curr.ptr = ptr\n",
    "        curr.size = len(w)\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        root = TrieNode()\n",
    "        for i, w in enumerate(smalls):\n",
    "            root.insert(w, i)\n",
    "        res = [[] for _ in range(len(smalls))]\n",
    "        for i in range(len(big)):\n",
    "            curr = root\n",
    "            for j in range(i, len(big)):\n",
    "                key = ord(big[j])-ord('a')\n",
    "                if curr.c[key] is None: break\n",
    "                if curr.c[key].ptr != -1:\n",
    "                    res[curr.c[key].ptr].append(j-curr.c[key].size+1)\n",
    "                curr = curr.c[key]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\"mis\"\n",
    "[\"is\"]\n",
    "\"\"\n",
    "[\"a\",\"b\",\"c\"]\n",
    "\"mississippi\"\n",
    "[\"is\",\"ppi\",\"hi\",\"sis\",\"i\",\"ssippi\"]\n",
    "\n",
    "0 <= len(big) <= 1000\n",
    "0 <= len(smalls[i]) <= 1000\n",
    "The total number of characters in smalls will not exceed 100000.\n",
    "No duplicated strings in smalls.\n",
    "All characters are lowercase letters.\n",
    "\"\"\"\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.c = [None]*26\n",
    "        self.ptr = -1\n",
    "        self.size = -1\n",
    "    def insert(self, w, ptr):\n",
    "        curr = self\n",
    "        for ch in w:\n",
    "            key = ord(ch)-ord('a')\n",
    "            if curr.c[key] is None:\n",
    "                curr.c[key] = TrieNode()\n",
    "            curr = curr.c[key]\n",
    "        curr.ptr = ptr\n",
    "        curr.size = len(w)\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        root = TrieNode()\n",
    "        for i, w in enumerate(smalls):\n",
    "            root.insert(w, i)\n",
    "        res = [[] for _ in range(len(smalls))]\n",
    "        for _ in range(len(big)):\n",
    "            curr = root\n",
    "            for i in range(_, len(big)):\n",
    "                key = ord(big[i])-ord('a')\n",
    "                if curr.c[key] is None: break\n",
    "                if curr.c[key].ptr != -1:\n",
    "                    res[curr.c[key].ptr].append(i-curr.c[key].size+1)\n",
    "                curr = curr.c[key]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_end_of_word = False\n",
    "        self.indexes = []\n",
    "\n",
    "def build_trie(smalls: List[str]) -> TrieNode:\n",
    "    root = TrieNode()\n",
    "    for i, small in enumerate(smalls):\n",
    "        node = root\n",
    "        for ch in small:\n",
    "            if ch not in node.children:\n",
    "                node.children[ch] = TrieNode()\n",
    "            node = node.children[ch]\n",
    "        node.is_end_of_word = True\n",
    "        node.indexes.append(i)\n",
    "    return root\n",
    "\n",
    "def search_in_trie(root: TrieNode, big: str, ans: List[List[int]]):\n",
    "    for i in range(len(big)):\n",
    "        node = root\n",
    "        j = i\n",
    "        while j < len(big) and big[j] in node.children:\n",
    "            node = node.children[big[j]]\n",
    "            if node.is_end_of_word:\n",
    "                for index in node.indexes:\n",
    "                    ans[index].append(i)\n",
    "            j += 1\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        root = build_trie(smalls)\n",
    "        ans = [[] for _ in range(len(smalls))]\n",
    "        \n",
    "        search_in_trie(root, big, ans)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# Test the function\n",
    "sol = Solution()\n",
    "big = \"mississippi\"\n",
    "smalls = [\"is\", \"s\", \"issi\", \"miss\"]\n",
    "print(sol.multiSearch(big, smalls))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        result = [[] for _ in range(len(smalls))]\n",
    "        n, trie = len(big), {}\n",
    "        for i, w in enumerate(smalls):\n",
    "            reduce(lambda d, c: d.setdefault(c, {}), w, trie)['!'] = (i, len(w))\n",
    "        def search(i, d):\n",
    "            if i < n and big[i] in d:\n",
    "                sub = d[big[i]]\n",
    "                if '!' in sub:\n",
    "                    j, x = sub['!']\n",
    "                    result[j].append(i-x+1)\n",
    "                search(i+1, sub)\n",
    "        any(search(i, trie) for i in range(n))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "        self.num = None\n",
    "\n",
    "class Solution:\n",
    "    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "        self.tree = Trie()\n",
    "        n = len(smalls)\n",
    "        res = [[] for _ in range(n)]\n",
    "\n",
    "        for i, small in enumerate(smalls):\n",
    "            node = self.tree\n",
    "            j = 0\n",
    "            while j < len(small):\n",
    "                idx = ord(small[j]) - ord('a')\n",
    "                if node.children[idx] is None:\n",
    "                    node.children[idx] = Trie()\n",
    "                node = node.children[idx]\n",
    "                j += 1\n",
    "            if j > 0:\n",
    "                node.num = i \n",
    "                node.isEnd = True\n",
    "\n",
    "\n",
    "        for i in range(len(big)):\n",
    "            node = self.tree\n",
    "            j = i\n",
    "            while j < len(big):\n",
    "                if node.isEnd == True:\n",
    "                    res[node.num].append(i)\n",
    "\n",
    "                idx = ord(big[j]) - ord('a')\n",
    "                if node.children[idx] is None:\n",
    "                    break\n",
    "                node = node.children[idx]\n",
    "                j += 1\n",
    "            \n",
    "            if node.isEnd == True and j == len(big):\n",
    "                print(i)\n",
    "                res[node.num].append(i)\n",
    "\n",
    "            \n",
    "            \n",
    "                \n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
